package 第一周;

import java.util.Arrays;

/**
 * @author xhw
 * @date 2024/3/17
 */

public class 寻找两个正序数组的中位数 {
    //给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
    //
    //算法的时间复杂度应该为 O(log (m+n)) 。
    //
    //
    //
    //示例 1：
    //
    //输入：nums1 = [1,3], nums2 = [2]
    //输出：2.00000
    //解释：合并数组 = [1,2,3] ，中位数 2
    //示例 2：
    //
    //输入：nums1 = [1,2], nums2 = [3,4]
    //输出：2.50000
    //解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
    //
    //
    //
    //
    //提示：
    //
    //nums1.length == m
    //nums2.length == n
    //0 <= m <= 1000
    //0 <= n <= 1000
    //1 <= m + n <= 2000
    //-106 <= nums1[i], nums2[i] <= 106

    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1, nums2));

        int[] nums3 = {1, 2};
        int[] nums4 = {3, 4};
        System.out.println(findMedianSortedArrays(nums3, nums4));

    }

    private static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //合并两个数组
        int[] nums = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        for (i = 0; i < nums1.length; i++) {
            nums[i] = nums1[i];
        }
        for (j = 0; j < nums2.length; j++) {
            nums[i + j] = nums2[j];
        }

        //排序拿到新数组
        Arrays.sort(nums);

        //计算中位数
        int midIndex = nums.length / 2;
        if (nums.length % 2 == 0){
            //如果有偶数个，则中位数为平均数
            return (double) (nums[midIndex - 1] + nums[midIndex]) / 2;
        } else {
            //如果是奇数个，则中位数是中间的那个数
            return nums[midIndex];
        }
    }
}
